package com.zql.LeetCode;

/**
 * Created By ShuHua on 2021/8/23.
 */
public class SearchRange_34 {
    public static int[] searchRange(int[] nums, int target) {
        return  new int[]{1,1};
    }

    /**
     * 寻找左侧边界-闭区间版
     * @param nums
     * @param target
     * @return
     */
    public static int Left_bound(int[] nums,int target){
        if (nums.length==0)return -1;
        int left = 0;
        int right = nums.length-1;

        while (left<=right){// left = right+1
            int mid = left + (right-left)/2;
            if(nums[mid] == target){
                right=mid-1;//闭区间值等于target时这里的值不能等mid 等于mid的话就会死循环，需要与其他条件中的right或者left相同
            }else if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left = mid+1;
            }
        }
        if(left==nums.length||nums[left]!=target) return -1;
        return left;
    }

    /**
     * 寻找左侧边界-左闭右开区间版
     * @param nums
     * @param target
     * @return
     */
    public static int Left_bound_open(int[] nums,int target){
        if (nums.length==0)return -1;
        int left = 0;
        int right = nums.length;

        while (left<right){// left = right
            int mid = left + (right-left)/2;
            if(nums[mid] == target){
                right=mid;
            }else if(nums[mid]>target){
                right=mid;
            }else if(nums[mid]<target){
                left = mid+1;
            }
        }
        if(left==nums.length||nums[left]!=target) return -1;
        return left;
    }

    /**
     * 寻找右侧边界-闭区间版
     * @param nums
     * @param target
     * @return
     */
    public static int right_bound(int[] nums,int target){
        if (nums.length==0)return -1;
        int left = 0;
        int right = nums.length-1;

        while (left<=right){// left = right+1
            int mid = left + (right-left)/2;
            if(nums[mid] == target){
                left=mid+1;
            }else if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }
        }
        if(right<0||right==nums.length||nums[right]!=target) return -1;
        return right;
    }

    /**
     * 寻找右侧边界-左闭右开区间版
     * @param nums
     * @param target
     * @return
     */
    public static int right_bound_open(int[] nums,int target){
        if (nums.length==0)return -1;
        int left = 0;
        int right = nums.length;

        while (left<right){// left = right
            int mid = left + (right-left)/2;
            if(nums[mid] == target){
                left=mid+1;//因为我们对left的更新是mid+1 所以循环结束之后nums[left]一定不等于target，
            }else if(nums[mid]>target){
                right=mid;
            }else if(nums[mid]<target){
                left=mid+1;
            }
        }
        if(right==0||right-1==nums.length||nums[right-1]!=target) return -1;
        return right-1;
    }


    /**
     * 二分搜索左右边界 最后返回啥根据 while的终止条件以及 nums[mid]==target后的条件操作
     * 如寻找右侧边界 左闭右开区间 while结束条件 left=right nums[mid]==target后的操作：left=mid+1 mid=left-1=right-1 因此返回left-1和right-1都一样
     * 如寻找右侧边接 闭区间 while结束条件 left=right+1 nums[mid]==target后的操作：left=mid+1 mid=left-1=right    因此可以返回left-1或者返回right
     * 如寻找左侧边界 左闭右开区间 while结束条件 left=right nums[mid]==target后的操作：right=mid   mid =right=left 所以返回right和left都可以
     * 如寻找左侧边界 闭区间 while结束条件 left=right+1 nums[mid]==target后的操作: right=mid-1  mid = right+1=left 所以返回left和返回right+1是一样的
     * target=nums[mid] 后的操作根据  left合适right根据搜索的是左区间还是右区间 搜索的是左区间 更新right 搜索的是右区间 更新left
     * 至于left和right等于谁 就根据else if 里面的一样就可以了
     * 注意如果返回right-1或者left-1时需要注意 left和right为0的边界情况
     * 如何判断越界 根据返回的left和right的取值范围
     * 如 右侧边界 开区间  返回 right-1  且 right=mid 那么right放入取值范围与mid相等【0，nums.length) 那么right-1的取值范围【-1，nums.length-1)
     * 如 右侧边界 闭区间  返回 right 且 right=mid-1 那么 right的取值范围为mid-1的范围 mid的取值范围为【0，nums.length-1】mid-1取值范围【-1，nums.length-2] 那么此时right会出现小于零的越界情况
     * @param args
     */


    public static void main(String[] args) {
        int[] nums = {1,2,2,2,3};
        int r1 = Left_bound(nums,2);
        int r2 = Left_bound_open(nums,2);
        System.out.println(r1);
        int ro1 = right_bound(nums,2);
        int ro2 = right_bound_open(nums,2);
        System.out.println(r2);
        System.out.println(ro1);
        System.out.println(ro2);
    }
}
